
package java.lang;

import jdk.internal.misc.TerminatingThreadLocal;

import java.lang.ref.WeakReference;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Supplier;


/**
 * 1、ThreadLocal解决线程局部变量统一定义问题，多线程数据不能共享，不能解决并发问题
 * 2、基于类级别的变量定义，每一个线程单独维护自己线程内的变量值（存、取、删的功能）
 */
public class ThreadLocal<T> {

    // 每个线程生成唯一的标识
    private final int threadLocalHashCode = nextHashCode();

    private static AtomicInteger nextHashCode = new AtomicInteger();
    private static final int HASH_INCREMENT = 0x61c88647; //散列算法-魔数0x61c88647


    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }


    //初始化值
    protected T initialValue() {
        return null;
    }

    public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
        return new SuppliedThreadLocal<>(supplier);
    }

    //构造函数
    public ThreadLocal() {
    }


    public void set(T value) {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if (map != null) {
            map.set(this, value);
        } else {
            createMap(t, value);
        }
    }


    public T get() {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if (map != null) {
            ThreadLocalMap.Entry e = map.getEntry(this);
            if (e != null) {
                @SuppressWarnings("unchecked")
                T result = (T) e.value;
                return result;
            }
        }
        return setInitialValue();
    }


    boolean isPresent() {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        return map != null && map.getEntry(this) != null;
    }

    private T setInitialValue() {
        T value = initialValue();
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if (map != null) {
            map.set(this, value);
        } else {
            createMap(t, value);
        }
        if (this instanceof TerminatingThreadLocal) {
            TerminatingThreadLocal.register((TerminatingThreadLocal<?>) this);
        }
        return value;
    }


    public void remove() {
        ThreadLocalMap m = getMap(Thread.currentThread());
        if (m != null) {
            m.remove(this);
        }
    }


    /**
     * 从线程中获取 ThreadLocalMap
     */
    ThreadLocalMap getMap(Thread t) {
        return t.threadLocals;
    }


    // 创建 ThreadLocalMap


    /**
     * 创建并初始化当前线程的线程局部变量映射
     * @param t 当前线程对象，用于在该线程中创建线程局部变量映射
     * @param firstValue 初始化线程局部变量映射时使用的第一个值
     */
    void createMap(Thread t, T firstValue) {
        // 初始化线程的threadLocals属性，为其分配一个新的ThreadLocalMap对象
        // ThreadLocalMap用于存储线程局部变量，确保每个线程都有自己的变量副本
        t.threadLocals = new ThreadLocalMap(this, firstValue);
    }

    static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
        return new ThreadLocalMap(parentMap);
    }


    T childValue(T parentValue) {
        throw new UnsupportedOperationException();
    }

    static final class SuppliedThreadLocal<T> extends ThreadLocal<T> {

        private final Supplier<? extends T> supplier;

        SuppliedThreadLocal(Supplier<? extends T> supplier) {
            this.supplier = Objects.requireNonNull(supplier);
        }

        @Override
        protected T initialValue() {
            return supplier.get();
        }
    }


    // 线性探测法实现的哈希表
    // 底层采用数组存储数据
    static class ThreadLocalMap {

        /**
         * 定义一个内部静态类Entry，用于表示ThreadLocal的引用表项
         * 该类继承自WeakReference<ThreadLocal<?>>，表示它将持有ThreadLocal的弱引用
         * 弱引用允许垃圾回收器在需要时回收ThreadLocal实例，以避免内存泄漏
         */
        static class Entry extends WeakReference<ThreadLocal<?>> {
            /**
             * 存储ThreadLocal的值
             * 每个Entry对象除了持有ThreadLocal的弱引用外，还包含一个与该ThreadLocal关联的具体值
             */
            Object value;

            /**
             * 构造方法，初始化Entry对象
             *
             * @param k ThreadLocal实例，作为键，使用弱引用持有
             * @param v ThreadLocal的值，可以是任意对象
             */
            Entry(ThreadLocal<?> k, Object v) {
                super(k);
                value = v;
            }
        }

        private static final int INITIAL_CAPACITY = 16;  //初始化 slot 数
        private Entry[] table;    //hash表数组
        private int size = 0;
        private int threshold;    //扩容参数，容量达到 2/3 就会出现扩容操作

        private void setThreshold(int len) {
            threshold = len * 2 / 3;
        }

        private static int nextIndex(int i, int len) {
            return ((i + 1 < len) ? i + 1 : 0);
        }

        private static int prevIndex(int i, int len) {
            return ((i - 1 >= 0) ? i - 1 : len - 1);
        }


        /**
         * 初始化ThreadLocalMap，包含一个ThreadLocal变量作为键和对应的值
         *
         * @param firstKey   第一个ThreadLocal变量，作为映射的键
         * @param firstValue 与firstKey关联的值
         */
        ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
            // 初始化一个具有初始容量的Entry数组作为哈希表
            // 初始化长度 16
            table = new Entry[INITIAL_CAPACITY];
            // 计算firstKey的哈希码，并使用位运算来确定在table数组中的索引位置
            int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);  //取余操作
            // 在计算出的索引位置上创建并放置一个新的Entry对象
            table[i] = new Entry(firstKey, firstValue);
            // 设置初始大小为1
            size = 1;
            // 设置重哈希的阈值，当元素数量达到此阈值时，将进行重哈希
            setThreshold(INITIAL_CAPACITY);
        }

        private ThreadLocalMap(ThreadLocalMap parentMap) {
            Entry[] parentTable = parentMap.table;
            int len = parentTable.length;
            setThreshold(len);
            table = new Entry[len];

            for (int j = 0; j < len; j++) {
                Entry e = parentTable[j];
                if (e != null) {
                    @SuppressWarnings("unchecked")
                    ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
                    if (key != null) {
                        Object value = key.childValue(e.value);
                        Entry c = new Entry(key, value);
                        int h = key.threadLocalHashCode & (len - 1);
                        while (table[h] != null)
                            h = nextIndex(h, len);
                        table[h] = c;
                        size++;
                    }
                }
            }
        }

        /**
         * 获取与指定ThreadLocal键关联的Entry
         * 此方法首先计算键的哈希码，并使用该哈希码找到对应的table索引
         * 然后检查该索引处的Entry是否为空或匹配给定的ThreadLocal键
         * 如果匹配成功，则直接返回该Entry；否则，调用另一个方法继续查找
         *
         * @param key 要获取Entry的ThreadLocal键
         * @return 关联的Entry，如果没有找到则返回null
         */
        private Entry getEntry(ThreadLocal<?> key) {
            // 计算ThreadLocal键的哈希码，并确定其在table数组中的索引位置
            int i = key.threadLocalHashCode & (table.length - 1);
            // 获取该索引位置的Entry
            Entry e = table[i];
            // 检查该位置的Entry是否为空或匹配给定的ThreadLocal键
            if (e != null && e.get() == key)
                // 如果匹配成功，则直接返回该Entry
                return e;
            else
                // 否则，调用另一方法继续在可能的位置查找Entry
                return getEntryAfterMiss(key, i, e);
        }

        /**
         * 当发生缓存未命中时，搜索并返回与指定ThreadLocal键关联的Entry.
         * 此方法在ThreadLocalMap中用于处理缓存未命中的情况. 它会遍历哈希表来查找与给定ThreadLocal键对应的Entry.
         * 如果找到匹配的Entry且其键与指定的ThreadLocal键相同，则返回该Entry.
         * 如果遇到已失效的Entry（即Entry的键为null），则将其移除以释放空间.
         *
         * @param key 指定的ThreadLocal键，用于查找对应的Entry.
         * @param i   初始探查索引，用于确定开始搜索的位置.
         * @param e   从给定索引开始的初始Entry，通常为table[i].
         * @return 返回与指定ThreadLocal键关联的Entry，如果未找到则返回null.
         */
        private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
            // 获取当前ThreadLocalMap的Entry数组
            Entry[] tab = table;
            // 获取Entry数组的长度
            int len = tab.length;
            // 遍历Entry数组，直到找到匹配的Entry或遍历结束
            while (e != null) {
                // 获取当前Entry的ThreadLocal键
                ThreadLocal<?> k = e.get();
                // 如果当前Entry的键与指定的ThreadLocal键相同，返回当前Entry
                if (k == key)
                    return e;
                // 如果当前Entry的键为null，说明该Entry已失效，需要移除
                if (k == null)
                    expungeStaleEntry(i);   // 缩容
                else
                    // 如果当前Entry的键不为null但不匹配，移动到下一个索引
                    i = nextIndex(i, len);
                // 更新当前Entry为下一个索引位置的Entry
                e = tab[i];
            }
            // 如果遍历结束仍未找到匹配的Entry，返回null
            return null;
        }

        /**
         * 设置ThreadLocal变量的值
         * 此方法负责在当前线程的ThreadLocalMap中为指定的ThreadLocal变量设置值
         * 如果变量已存在，则更新其值；如果变量不存在，则添加新的映射项
         *
         * @param key   ThreadLocal变量，作为映射的键
         * @param value 要设置的值，作为映射的值
         */
        private void set(ThreadLocal<?> key, Object value) {
            // 获取当前线程的ThreadLocalMap中的条目数组
            Entry[] tab = table;
            // 获取条目数组的长度
            int len = tab.length;
            // 计算ThreadLocal变量的索引位置
            int i = key.threadLocalHashCode & (len - 1);

            // 遍历条目数组，查找匹配的ThreadLocal变量
            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                ThreadLocal<?> k = e.get();

                // 如果找到匹配的ThreadLocal变量，更新其值并返回
                if (k == key) {
                    e.value = value;
                    return;
                }

                // 如果遇到空的ThreadLocal引用，替换为新的映射项
                if (k == null) {
                    replaceStaleEntry(key, value, i);
                    return;
                }
            }

            // 如果未找到匹配项，添加新的映射项到条目数组
            tab[i] = new Entry(key, value);
            // 增加map大小，并检查是否需要重新哈希
            int sz = ++size;
            if (!cleanSomeSlots(i, sz) && sz >= threshold)
                rehash();
        }

        private void remove(ThreadLocal<?> key) {
            Entry[] tab = table;
            int len = tab.length;
            int i = key.threadLocalHashCode & (len - 1);
            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                if (e.get() == key) {
                    e.clear();
                    expungeStaleEntry(i);
                    return;
                }
            }
        }

        private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                                       int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;
            Entry e;

            // Back up to check for prior stale entry in current run.
            // We clean out whole runs at a time to avoid continual
            // incremental rehashing due to garbage collector freeing
            // up refs in bunches (i.e., whenever the collector runs).
            int slotToExpunge = staleSlot;
            for (int i = prevIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = prevIndex(i, len))
                if (e.get() == null)
                    slotToExpunge = i;

            // Find either the key or trailing null slot of run, whichever
            // occurs first
            for (int i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal<?> k = e.get();

                // If we find key, then we need to swap it
                // with the stale entry to maintain hash table order.
                // The newly stale slot, or any other stale slot
                // encountered above it, can then be sent to expungeStaleEntry
                // to remove or rehash all of the other entries in run.
                if (k == key) {
                    e.value = value;

                    tab[i] = tab[staleSlot];
                    tab[staleSlot] = e;

                    // Start expunge at preceding stale entry if it exists
                    if (slotToExpunge == staleSlot)
                        slotToExpunge = i;
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                    return;
                }

                // If we didn't find stale entry on backward scan, the
                // first stale entry seen while scanning for key is the
                // first still present in the run.
                if (k == null && slotToExpunge == staleSlot)
                    slotToExpunge = i;
            }

            // If key not found, put new entry in stale slot
            tab[staleSlot].value = null;
            tab[staleSlot] = new Entry(key, value);

            // If there are any other stale entries in run, expunge them
            if (slotToExpunge != staleSlot)
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }


        private int expungeStaleEntry(int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;

            // expunge entry at staleSlot
            tab[staleSlot].value = null;
            tab[staleSlot] = null;
            size--;

            // Rehash until we encounter null
            Entry e;
            int i;
            for (i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal<?> k = e.get();
                if (k == null) {
                    e.value = null;
                    tab[i] = null;
                    size--;
                } else {
                    int h = k.threadLocalHashCode & (len - 1);
                    if (h != i) {
                        tab[i] = null;

                        // Unlike Knuth 6.4 Algorithm R, we must scan until
                        // null because multiple entries could have been stale.
                        while (tab[h] != null)
                            h = nextIndex(h, len);
                        tab[h] = e;
                    }
                }
            }
            return i;
        }


        private boolean cleanSomeSlots(int i, int n) {
            boolean removed = false;
            Entry[] tab = table;
            int len = tab.length;
            do {
                i = nextIndex(i, len);
                Entry e = tab[i];
                if (e != null && e.get() == null) {
                    n = len;
                    removed = true;
                    i = expungeStaleEntry(i);
                }
            } while ((n >>>= 1) != 0);
            return removed;
        }


        private void rehash() {
            expungeStaleEntries();

            // Use lower threshold for doubling to avoid hysteresis
            if (size >= threshold - threshold / 4)
                resize();
        }


        private void resize() {
            Entry[] oldTab = table;
            int oldLen = oldTab.length;
            int newLen = oldLen * 2;
            Entry[] newTab = new Entry[newLen];
            int count = 0;

            for (int j = 0; j < oldLen; ++j) {
                Entry e = oldTab[j];
                if (e != null) {
                    ThreadLocal<?> k = e.get();
                    if (k == null) {
                        e.value = null; // Help the GC
                    } else {
                        int h = k.threadLocalHashCode & (newLen - 1);
                        while (newTab[h] != null)
                            h = nextIndex(h, newLen);
                        newTab[h] = e;
                        count++;
                    }
                }
            }

            setThreshold(newLen);
            size = count;
            table = newTab;
        }

        /**
         * Expunge all stale entries in the table.
         */
        private void expungeStaleEntries() {
            Entry[] tab = table;
            int len = tab.length;
            for (int j = 0; j < len; j++) {
                Entry e = tab[j];
                if (e != null && e.get() == null)
                    expungeStaleEntry(j);
            }
        }
    }
}
